/* This program calculates the selection of coins needed to return change based
 * on the coins available */
#include <stdio.h>

/* We cheat. Infinity is >= 9999 */
#define INFINITY 9999

/* Set of coins - (value, count) */
struct coin {
	int value;
	int count;
};

struct coin coins[] = {
	{1, 4},
	{3, 2},
	{4, 2},
	{5, 1},
};

/* Number of denominations */
int num = 4;
int counts[100];

/* used[i][j] tells us how many coins of denom i were used to achieve sum j */
int used[100][100];
int dp[100][100];

/* Print a (m x n) array */
void print_arr(int arr[][100], int m, int n)
{
	int i,j;

	printf("%4d | ",0);
	for(j=0; j < n; j++)
		printf("%4d ",j);
	printf("\n");

	printf("-------");
	for(j=0; j < n; j++)
		printf("-----");
	printf("\n");

	for (i = 0; i < m; i++) {
		printf("%4d | ", coins[i].value);

		for (j=0; j < n; j++) {
			if (arr[i][j] == INFINITY)
				printf("%4c ", '%');
			else
				printf("%4d ", arr[i][j]);
		}
		printf("\n");
	}
	printf("\n");
}

void initialize(int sum, int k)
{
	int i, j;

	/* Initialize the dynamic programming array with a set of 1 coin of
	 * denom 1. We need j coins to realise sum j. If j is greater than
	 * available coins, then its not possible. i.e. we need INFINITY coins
	 */
	/* TODO: Fix this for when 1st coin is not of denom 1 */
	for(j = 1; j <= sum; j++) {
		dp[0][j] = j > coins[0].count ? INFINITY : j;

		if(dp[0][j] == INFINITY)
			used[0][j] = 0;
		else
			used[0][j] = j;
	}

	/* To realise a sum of 0, we need 0 coins for any denomination */
	for (i=0; i < k; i++)
		dp[i][0] = 0;
}

void change(int sum, int k)
{
	int i,j;

	for (i = 1; i < k; i++) {
		for (j = 1; j <= sum; j++) {
			/* The current coin being considered is greater than
			 * the current sum. We can't add it */
			if (coins[i].value > j) {
				dp[i][j] = dp[i-1][j];
				used[i][j] = 0;
			} else {
				/* Compare adding the coin or not adding it.
				   We know that the current sum can be realised
				   by using coins from only from the set 0-i-1.
				   That value is saved in (i-1, j) If we are to
				   use the current coin and realise this sum we
				   have to add it to the value of (sum -
				   current coin) realised with 0..i-1 coins
				 */
				int prev_min = dp[i-1][j];
				int new_min = 1 + dp[i][j - coins[i].value];

				if(new_min < prev_min) {
					/* Adding the new coin is better than
					 * the previous min */
					int needed = used[i][j - coins[i].value] + 1;
					if (needed <= coins[i].count) {
						dp[i][j] = dp[i][j-coins[i].value] + 1;
						used[i][j] = needed;
					} else {
						dp[i][j] = dp[i-1][j-coins[i].value] + 1;
						used[i][j] = 1;
					}
				} else {
					dp[i][j]= prev_min;
					used[i][j] = 0;
				}
			}
		}
	}
}

void retrace(int sum, int k)
{
	int i = k, j = sum;
	int x;

	if (dp[i][j] >= INFINITY) {
		printf("\n!!No solution\n");
		return;
	}

	if(sum == 0) {
		printf("\n");
		return;
	}

	if (used[i][j] == 0) {
		retrace(sum, k-1);
	} else {
		for(x = used[i][j]; x > 0; x--)
			printf("%d ", coins[i].value);

		retrace(sum - (coins[i].value * used[i][j]), k - 1);
	}
}

int main(int argc, char **argv)
{
	int sum = 17, num = 4;

	printf("Enter sum to test: ");
	scanf("%d", &sum);

	initialize(sum, num);
	change(sum, num);
	print_arr(dp, num, sum+1);
	print_arr(used, num, sum+1);

	retrace(sum, num-1);

	return 0;
}

